package algorithm.middle;

import static algorithm.middle.CanPartitionKSubsets698.count;

/**
 * 给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。
 *
 * 你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。
 *
 * 请你返回使 s 平衡 的 最少 删除次数。
 */
public class MinimumDeletions1653 {

    /**
     * 前后缀分解
     * 分支预测
     */
    public int minimumDeletions(String s) {
        char[] array = s.toCharArray();
        //统计所有a的个数
        int countA = 0;
        for (char c : array) {
//            if (c=='a') countA++;
            countA += 'b' - c;
        }
        int res = countA;
        //再次便利，当前字符为a则减1，为b则加1
        for (char c : array) {
//            if (c=='a'){
//                countA--;
//            }else {
//                countA++;
//            }
            //使用位运算，避免cpu分支预测
            countA += (c - 'a') * 2 - 1;
            res = Math.min(res, countA);
        }
        return res;
    }
}
